int isCC(QImage *orig, QImage *dest, int x, int y) {
	if (x < 0 || x >= orig->width())
		return 0;
	if (y < 0 || y >= orig->height())
		return 0;
	if (((int)qRed(orig->pixel(x,y))) == 255)
	   	return 0;
	if (((int)qRed(dest->pixel(x,y))) == 0)
	   	return 0;
	
	if (getBlack(dest, x+1, y))
	   	return 1;
	if (getBlack(dest, x-1, y))
	   	return 1;
	if (getBlack(dest, x, y+1))
	   	return 1;
	if (getBlack(dest, x, y-1))
	   	return 1;

	if (getBlack(dest, x+1, y+1))
	   	return 1;
	if (getBlack(dest, x+1, y-1))
	   	return 1;
	if (getBlack(dest, x-1, y+1))
	   	return 1;
	if (getBlack(dest, x-1, y-1))
	   	return 1;
   	return 0;
}

void findCC(QImage *orig, QImage *dest, int x1, int y1) {
	for( int y = 0; y < orig->height(); ++y ){
		for( int x = 0; x < orig->width(); ++x ){
		   dest->setPixel(x, y, QColor(255,255,255).rgb());
		}
	}
	dest->setPixel(x1, y1, QColor(0,0,0).rgb());

	int changed = 1;
	for (int i=0; changed == 1 && i<1000; i++) { //1000 é so uma protecao
	   changed = 0;
	   for( int y = 0; y < orig->height(); ++y )
		  for( int x = 0; x < orig->width(); ++x )
			 if (isCC(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	   for( int x = 0; x < orig->width(); ++x )
		  for( int y = 0; y < orig->height(); ++y )
			 if (isCC(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	   for( int y = orig->height()-1; y >= 0; --y )
		  for( int x = orig->width(); x>=0; --x )
			 if (isCC(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	   for( int x = orig->width(); x>=0 ; --x )
		  for( int y = orig->height()-1; y >= 0; --y )
			 if (isCC(orig, dest, x, y)) {
				dest->setPixel(x, y, QColor(0,0,0).rgb());
				changed = 1;
			 }
	}
}

int findCCs(QImage *orig, QImage *dest) {
   	int stop = 0;
	for( int y = 0; !stop && y < orig->height(); ++y ){
		for( int x = 0; !stop && x < orig->width(); ++x ){
		   int px = qRed(orig->pixel(x,y));
		   	if (px == 0) {
				findCC(orig, dest, x, y);
				stop = 1;
			}
		}
	}
	if (stop == 0)
		return 0;

	for( int y = 0; y < orig->height(); ++y ){
		for( int x = 0; x < orig->width(); ++x ){
			int px = qRed(dest->pixel(x,y));
			if (px == 0)
			   orig->setPixel(x, y, QColor(255,255,255).rgb());
		}
	}
	return 1;
}

void saveImage(QImage *img, QString name, const char *ext) {
   	int x0=0, y0=0, xf=0, yf=0, saida;

	saida = 0;
	for( int y = 0; !saida && y < img->height(); ++y )
	   for( int x = 0; !saida && x < img->width(); ++x )
		  if (((int)qRed(img->pixel(x,y))) < 255) {
			 y0 = y;
			 saida = 1;
		  }

	saida = 0;
	for( int x = 0; !saida && x < img->width(); ++x )
	   for( int y = 0; !saida && y < img->height(); ++y )
		  if (((int)qRed(img->pixel(x,y))) < 255) {
			 x0 = x;
			 saida = 1;
		  }

	saida = 0;
	for( int y = img->height()-1; !saida && y >= 0 ; --y )
	   for( int x = 0; !saida && x < img->width(); ++x )
		  if (((int)qRed(img->pixel(x,y))) < 255) {
			 yf = y;
			 saida = 1;
		  }

	saida = 0;
	for( int x = img->width()-1; !saida && x >= 0; --x )
	   for( int y = 0; !saida && y < img->height(); ++y )
		  if (((int)qRed(img->pixel(x,y))) < 255) {
			 xf = x;
			 saida = 1;
		  }

	int width=xf-x0, height=yf-y0;
	if (width > 0 && height > 0)
	   img->copy(x0,y0,width,height).save(name, ext);
}
void NewspaperSegmentation::computeStep5Image(){
	if( image_step[4] == 0 )
		computeStep4Image();
	if( image_step[5] ){
		setCurrentImage( 5 );
		return;
	}





	/*
	QImage *tmp = new QImage( image_step[4]->width(), image_step[4]->height(), QImage::Format_RGB32 );
	QImage *tmp2 = new QImage( image_step[4]->width(), image_step[4]->height(), QImage::Format_RGB32 );
	QImage *tmp3 = new QImage( image_step[4]->width(), image_step[4]->height(), QImage::Format_RGB32 );
	for( int y = 0; y < tmp->height(); ++y )
		for( int x = 0; x < tmp->width(); ++x )
			   tmp->setPixel(x,y, image_step[4]->pixel(x,y));

	//SAVE the result images!!!
	for (int i = 0; findCCs(tmp, tmp2); i++) {
	   for( int y = 0; y < tmp3->height(); ++y ){
		  for( int x = 0; x < tmp3->width(); ++x ){
			 if (((int)qRed(tmp2->pixel(x,y)) == 0))
				tmp3->setPixel(x,y, image_step[0]->pixel(x,y));
			 else
				tmp3->setPixel(x,y, QColor(255,255,255).rgb());
		  }
	   }
	   saveImage(tmp3, QString("/tmp/result%1.png").arg(i), "png");
	}
	*/

	image_step[5] = new QImage(image_step[4]->width(), image_step[4]->height() , QImage::Format_RGB32 );
	for( int y = 0; y < image_step[5]->height(); ++y ){
		for( int x = 0; x < image_step[5]->width(); ++x ){
			int px = qRed(image_step[4]->pixel(x,y));
			if (px == 0)
			   image_step[5]->setPixel(x,y, image_step[0]->pixel(x,y));
			else
			   image_step[5]->setPixel(x,y, QColor(0,255,0).rgb());
		}
	}
	//término da implementação
	setCurrentImage( 5 );
	
}
